#pragma once

#include <iostream>
#include <vector>
#include <unordered_set>

struct Location
{
	int x, y;
	Location direction() const; // const表示这个函数是一个常量成员函数，它不会修改对象的任何成员变量。这意味着你可以在常量对象上调用这个函数。
};

/* 声明我们将重载Location对象的这些操作符 */
bool operator==(const Location& a, const Location& b) noexcept;
bool operator!=(const Location& a, const Location& b) noexcept;
bool operator<(const Location& a, const Location& b) noexcept;
Location operator+(const Location& a, const Location& b) noexcept;
Location operator-(const Location& a, const Location& b) noexcept;
Location operator-(const Location& a) noexcept;
Location operator*(const int a, const Location& b) noexcept;
Location operator*(const Location& a, const int b) noexcept;
// 重载了输出运算符<<，允许Location对象被输出到std::ostream类型的流中，如标准输出流std::cout
std::ostream& operator<<(std::ostream& os, const Location& a);

// 常量，用于表示无效位置
const Location NoneLoc {-1, -1};

/* implement hash function so we can put Location into an unordered_set */
namespace std
{
	// 将代码块置于std命名空间中。在C++中，std是标准库的命名空间。

	// template <>表示这是一个模板特化。模板特化是针对特定类型对模板进行的完全定制实现。普通模板是泛型的，适用于多种类型，而模板特化则是为特定类型提供专门的实现。
	// struct hash<Location> 表示对std::hash模板类进行特化，使其能够处理Location类型。std::hash是一个模板类，用于生成不同类型Object的哈希值，在这里为其添加对Location类型的支持。
	template <> struct hash<Location>
	{
		// 这两行typedef代码删去也是可以的，只是在一些第三方库或者框架中可能会使用它们
		// typedef Location argument_type;
		// typedef std::size_t result_type;

		// 这是对函数调用运算符()的重载。通过重载这个运算符，使得该结构体的对象可以像函数一样被调用。
		// 形参表后的const表示这个函数是一个常量成员函数，不会修改对象的任何成员变量。
		// noexcept表示这个函数不会抛出异常，这是一个异常说明符，用于告知编译器和使用者该函数不会产生异常，有助于优化和错误处理。
		std::size_t operator() (const Location& id) const noexcept
		{
			// 疑问，为什么这里我们需要用(id.x ^ (id.y << 4))的值去构造1个std::hash object，再返回hashObj的值呢？
			// 我们直接把(id.x ^ (id.y << 4))的数据类型转换为size_t并返回不行吗？

			// 答：可以是可以，但这样生成的hash值质量更低，更容易冲突；
			// 例如id.x = 1且id.y = 2，那么(id.x ^ (id.y << 4)) = 33
			// 若std::size_t是64位的，那么高32位将始终为0
			// 而构造成std::hash object后，std::hash<int>会将33映射到一个64位的std::size_t值，确保生成的哈希值在整个std::size_t范围内均匀分布，这样hash冲突的可能性就更小。

			// unordered_set等容器内部，自己有处理哈希冲突的机制
			return std::hash<int>()(id.x ^ (id.y << 4));
		}
	};
}

class Grid
{
private:
	int width, height;

public:
	std::unordered_set<Location> walls;

	Grid(int width_, int height_, std::unordered_set<Location> walls_) : width(width_), height(height_), walls(walls_) {};

	int get_width() const {return width;};
	int get_heigth() const {return height;};

	// 判断点位是否在地图范围内
	bool in_bounds(const Location& loc) const noexcept { return 0 <= loc.x && loc.x < width && 0 <= loc.y && loc.y < height; };
	// 通过判断walls里面有没有loc来得出点位是否为阻挡，注意，Location的==运算符是重载过的
	bool passable(const Location& loc) const { return walls.find(loc) == walls.end(); };
	// 从loc往dir方向的移动是否是允许的（主要是判断阻挡情况）
	bool valid_move(const Location& loc, const Location& dir) const;
	// 判断neighbor是否为loc的强制邻居，travel_dir为loc的当前行进方向
	bool forced(const Location& neighbor, const Location& loc, const Location& travel_dir) const;

	// 取current在多个方向上（dirs）的邻居们
	std::vector<Location> neighbours(const Location& current, const std::vector<Location>& dirs) const;
	// 按jps对邻居的修剪规则，取修剪后剩下的邻居们（包括强制邻居）
	std::vector<Location> pruned_neighbours(const Location& current, const Location& parent) const;
};
